| 1. Identificação | |
| Tipo de Referência | Tese ou Dissertação (Thesis) |
| Site | mtc-m16c.sid.inpe.br |
| Código do Detentor | isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S |
| Identificador | 8JMKD3MGP8W/35E5B3P |
| Repositório | sid.inpe.br/mtc-m18@80/2009/06.04.19.56 (acesso restrito) |
| Última Atualização | 2024:04.23.15.09.55 (UTC) simone |
| Repositório de Metadados | sid.inpe.br/mtc-m18@80/2009/06.04.19.56.41 |
| Última Atualização dos Metadados | 2024:04.23.15.10.47 (UTC) simone |
| Chave Secundária | INPE-3075-TDI/161 |
| Chave de Citação | D´Ippolito:1983:ÁrPrVi |
| Título | Árvores de procura virtual compacta e ávores binárias com endereços ordenados para organização de arquivos  |
| Título Alternativo | x |
| Curso | CAP-SPG-INPE-BR |
| Ano | 1983 |
| Data | 1983-12-09 |
| Data de Acesso | 18 maio 2024 |
| Tipo da Tese | Dissertação (Mestrado em Computação Aplicada) |
| Tipo Secundário | TDI |
| Número de Páginas | 99 |
| Número de Arquivos | 1 |
| Tamanho | 13140 KiB |
| 2. Contextualização | |
| Autor | D´Ippolito, Eliane |
| Grupo | CAP-SPG-INPE-BR |
| Banca | Renna e Souza, Celso de (presidente) Seehusen, Hans Jurgen (orientador) Dias, Luiz Alberto Vieira Velasco, Paulo Augusto Silva Buss Filho, Arry Carlos |
| Universidade | Instituto Nacional de Pesquisas Espaciais (INPE) |
| Cidade | São José dos Campos |
| Histórico (UTC) | 2009-06-09 19:29:45 :: alessandra@sid.inpe.br -> marciana :: 2009-06-10 12:41:41 :: marciana -> alessandra@sid.inpe.br :: 2009-06-17 16:54:51 :: alessandra@sid.inpe.br -> administrator :: 2009-07-07 16:16:01 :: administrator -> marciana :: 2009-11-04 14:25:07 :: marciana -> administrator :: 2010-05-11 01:42:06 :: administrator -> alessandra@sid.inpe.br :: 2011-02-25 13:43:53 :: alessandra@sid.inpe.br -> carol@sid.inpe.br :: 2012-02-10 15:29:51 :: carol@sid.inpe.br -> viveca@sid.inpe.br :: 1983 2012-02-29 17:43:45 :: viveca@sid.inpe.br -> administrator :: 1983 2013-10-12 22:26:47 :: administrator -> sergio :: 1983 2014-02-04 14:40:31 :: sergio -> administrator :: 1983 2016-06-04 22:31:36 :: administrator -> sergio :: 1983 2016-10-17 11:59:05 :: sergio -> administrator :: 1983 2018-06-04 04:23:10 :: administrator -> sergio :: 1983 2019-12-12 18:27:49 :: sergio -> administrator :: 1983 2020-04-28 17:48:40 :: administrator -> simone :: 1983 2024-04-23 15:10:47 :: simone -> :: 1983 |
| 3. Conteúdo e estrutura | |
| É a matriz ou uma cópia? | é a matriz |
| Estágio do Conteúdo | concluido |
| Transferível | 1 |
| Palavras-Chave | organização de arquivos árvore de procura binária balanceamento número médio de acessos tempo de acesso taxa média de transferência |
| Resumo | Um estudo de dois tipos de árvore de procura binária é apresentado. Primeiramente, Árvores Binárias com Endereços Ordenados usando Árvores Virtuais para balanceamento foram implementadas com acesso direto em disco. Simulações feitas no CYBER 170/750 apresentam uma redução da taxa média de transferência na ordem de 50% para blocos de tamanho realístico (500 {{{{"bytes").}}}} Testes em microcomputador, sem multiprogramação ( Scopus uC 10) e com armazenamento da árvore em disquetes (tamanho do bloco de 128 {{{{"bytes"),}}}} apresentaram 40% de redução do tempo total de procura. A segunda árvore de procura binária analisada é a Árvore de Procura Virtual Compacta (APVC), desenvolvida neste trabalho. Uma APVC é basicamente uma Árvore Binária Virtual cm folhas adicionais contendo as chaves reais e os registros. Todos os nós internos da APVC tem grau 2, o que garante uma utilização ótima de armazenamento. O número médio de acessos é pouco maior (aproximadamente 2) que o de outras árvores balanceadas. Incersões e eliminações, mantendo a estrutura de acesso, são muito eficientes (0.7-0.3 acessos adicionais para atualização por inserção/eliminação. Por causa da separação entre a árvore de procura (somente ponteiros) e as informações reais (chave e registro), as APVCs são especialmente úteis para sistemas de armazenamento hierarquico. Simulações feitas com acesso direto em disco, utlizando endereços ordenados e APVCs, mostram que a redução da taxa média de transferência de blocos por procura é significante se o tamanho do registro é maior que 2 vzes o tamanho do endereço dos nós. ABSTRACT: A study of two types of binary search trees has been done. First, Addressed Ordered Binary Trees using Virtual Trees for balancing has been implemented with direct disc access. Simulations done on the CYBER170/750 show a reduction of the block transfer rate of the oder of 50% for realistic block sizes (500 bytes). Tests with a single user microcomputer (Scopus uC 10) with disquettes (blocksize about128 bytes) show that 40% of the total search time can be saved. The second binary search tree analized is the Compacted Virtual Search Tree (CVST), developed in this work. A CVST is basically a Virtual Binary Tree with additional leaves containing the actual keys and records. All internal nodes of a CVST have a degree of 2, which guarantees an optimal storage usage. The mean access number is slightly higher (about 2) than those of other balanced trees. Insertions and deletions (maintaining the tree structure) are very efficient (0.7/0.3 addicional write accesses por incertion/deletion). Because on the separation of the search tree (just pointers) an the actual information (Key and record), a CVST {{{{}}}} is especially useful for hierarchical storage systems. Simulations have been done with direct access, using CVST as well as address ordering . The reduction of the mean block transfer rate per search is significant if the record size is more than 2 times the lenght of the pointers. |
| Área | COMP |
| Arranjo | urlib.net > BDMCI > Fonds > Produção pgr ATUAIS > CAP > Árvores de procura... |
| Conteúdo da Pasta doc | acessar |
| Conteúdo da Pasta source | não têm arquivos |
| Conteúdo da Pasta agreement | não têm arquivos |
| 4. Condições de acesso e uso | |
| Idioma | pt |
| Arquivo Alvo | publicacao.pdf |
| Grupo de Usuários | administrator alessandra@sid.inpe.br marciana sergio |
| Grupo de Leitores | administrator simone |
| Visibilidade | shown |
| Detentor dos Direitos | originalauthor yes locatedauthor no |
| Permissão de Leitura | deny from all |
| Permissão de Atualização | não transferida |
| 5. Fontes relacionadas | |
| Repositório Espelho | sid.inpe.br/mtc-m18@80/2008/03.17.15.17.24 |
| Unidades Imediatamente Superiores | 8JMKD3MGPCW/3F2PHGS |
| Acervo Hospedeiro | sid.inpe.br/mtc-m18@80/2008/03.17.15.17 |
| 6. Notas | |
| Campos Vazios | academicdepartment affiliation archivingpolicy archivist callnumber contenttype copyholder copyright creatorhistory descriptionlevel dissemination doi e-mailaddress electronicmailaddress format isbn issn label lineage mark nextedition notes number orcid parameterlist parentrepositories previousedition previouslowerunit progress resumeid schedulinginformation secondarydate secondarymark session shorttitle sponsor subject tertiarymark tertiarytype url versiontype |